// https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/

// 算法思路总结：
// 1. 使用动态规划统计等差子序列数量
// 2. dp[i][j]表示以nums[i]、nums[j]结尾的等差序列个数
// 3. 哈希表记录每个数值的所有出现位置
// 4. 累加所有满足条件的等差序列数量
// 5. 时间复杂度：O(n²)，空间复杂度：O(n²)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    typedef long long ll;
    int numberOfArithmeticSlices(vector<int>& nums) 
    {
        int m = nums.size();
        if (m <= 2)
            return 0;

        vector<vector<int>> dp(m, vector<int>(m, 0));
        unordered_map<ll, vector<int>> up;
        int ret = 0;

        for (int i = 0; i < m - 1; i++) 
        {
            for (int j = i + 1; j < m; j++) 
            {
                ll b = nums[i], c = nums[j];
                ll a = 2 * b - c;
                if (up.count(a)) 
                {
                    for (int k = 0 ; k < up[a].size() ; k++)
                    {
                        dp[i][j] += dp[up[a][k]][i] + 1;
                    }
                    ret += dp[i][j];
                }
            }
            up[nums[i]].push_back(i);
        }

        return ret;
    }
};

int main()
{
    vector<int> v1 = {2,4,6,8,10}, v2 = {7,7,7,7,7};
    Solution sol;

    cout << sol.numberOfArithmeticSlices(v1) << endl;
    cout << sol.numberOfArithmeticSlices(v2) << endl;

    return 0;
}